package com.michael.demos.base.java.other;

import java.util.Arrays;

/**
 * @author Michael
 * @version 1.0
 * @date 2021/1/25 16:48
 */
public class 面试好题 {

    public static void main(String[] args) {

        //test();
        数字交换位置();
        //进制转换问题();
        //用异或找奇数个数字的问题();

    }

    public static void test() {

        int a = 123567;
        int b = 234234;

        String bina = Integer.toBinaryString(a);
        String binb = Integer.toBinaryString(b);
        String result = Integer.toBinaryString(a ^ b);
        System.out.format("%s ^ \n%s = \n%s", bina, binb, result);

    }

    public static void 进制转换问题() {
        Integer source = 98234701;
        String result = Integer.toHexString(source);

        System.out.println(result);

        System.out.println(Integer.valueOf("5daf14d", 16));
    }

    public static void 数字交换位置() {

        int a = 123567;
        int b = 234234;

        int[] arr = new int[]{a, b};

        System.out.println("原数组：" + Arrays.toString(arr));

        arr[0] = arr[0] + arr[1];
        arr[1] = arr[0] - arr[1];
        arr[0] = arr[0] - arr[1];

        System.out.println("使用加减法替换：" + Arrays.toString(arr));

        arr[0] = arr[0] ^ arr[1];
        arr[1] = arr[0] ^ arr[1];
        arr[0] = arr[0] ^ arr[1];

        System.out.println("使用异或替换：" + Arrays.toString(arr));
    }

    public static void 用异或找奇数个数字的问题() {

        // 只能有一个数为奇数个，假设数组中有10亿个数字
        int[] arr = new int[]{1, 2, 9, 9, 3, 4, 1, 2, 3, 4, 5, 5, 7, 7, 9};

        int result = arr[0];
        // 最优算法 —— 时间复杂度O(n)
        for (int i = 1; i < arr.length; i++) {
            result ^= arr[i];
        }
        System.out.println(result);

    }
}
